/* 最接近点对问题
一种可行方法是枚举法，时间复杂度O(N^2)，不是好的算法。
注意到问题的子结构性质（globalmin=min{all subsetmin}）考虑用分治法。
*/

#include <cstdio>

/* 一维点集最接近点对（伪代码） */
bool Cpair1(S, d) {
    n = S.size();
    if (n < 2) {
        d = INF;
        return false;
    }
    m = midnum(S);
    S1 = S[:m];
    S2 = S[m:];
    Cpair1(S1, d1);
    Cpair1(S2, d2);
    p = max(S1);
    q = min(S2);
    d = min(d1, d2, q-p);
    return true;
}